package com.cat.dataStructure;

/**
 * @author 曲大人的喵
 * @description https://leetcode.cn/problems/plates-between-candles/description/
 * @create 2025/8/16 10:16
 * @since JDK17
 */

public class Solution24 {
    //
    int find(int[] h, int r, int target) {
        int l = -1, mid;
        while (l + 1 < r) {
            mid = l + (r - l) / 2;
            if (h[mid] >= target) {
                r = mid;
            } else {
                l = mid;
            }
        }
        return r;
    }


    public int[] platesBetweenCandles(String s, int[][] queries) {
        int n = s.length(), m = queries.length, cnt = 0;
        int[] ans = new int[m], prefix = new int[n + 1], h = new int[n];
        for (int i = 0; i < n; i++) {   // 前缀和
            prefix[i + 1] = prefix[i] + (s.charAt(i) == '*' ? 1 : 0);
            if (s.charAt(i) == '|') {   // 记录一下|的位置
                h[cnt++] = i;
            }
        }

        for (int i = 0, l, r, j; i < m; i++) {
            l = queries[i][0];
            r = queries[i][1];
            j = find(h, cnt, l);    // 找到第一个
            while (h[j + 1] <= r) {
                ans[i] += prefix[h[j + 1]] - prefix[h[j]];
                j++;
            }
        }
        return ans;
    }
}
